Alorithm Cheat Sheet|算法Cheat Sheet

持续记录

Alorithm Cheat Sheet|算法Cheat Sheet

技巧|Tricks

  • while(~scanf("%d", &n))

    ~是按位取反 scanf的返回值是输入值的个数 如果没有输入值就是返回-1 -1按位取反结果是0,即没有输入的时候退出循环

  • INF(最大值)设置

    INF设为0x7fffffff：32-bit int的最大值，但是注意越界操作，且不能满足“无穷大加一个有穷的数依然是无穷大”条件

    INF设为0x3f3f3f3f：多数情况下较为合理，它是很大的数，方便数组清零操作memset(a,0x3f,sizeof(a))，且满足无穷大加无穷大还是无穷大的条件

素数表生成|Prime number table

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void createprime(int n)
{
	int m = sqrt(n + 0.5);
	memset(vis, 0, sizeof(vis));
	vis[1] = 1;
	for (int i = 2; i <= m; i++)
	    if (!vis[i])
		for (int j = i*i; j <= n; j += i)
		     vis[j] = 1;
}
/*生成1到n的素数表，里面的循环是把非素数置为1，素数为0,1特殊对待，直接赋值为1，变为非素数*/


bool isPrime_2(int num)
{
	if (num == 1)return 0;
	int tmp = sqrt(num);
	for (int i = 2; i <= tmp; i++)
		if (num %i == 0)
			return 0;
	return 1;
}
/*素数判断，对1特殊对待*/

快速幂|Binary Exponentiation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<stdio.h>
int fastPower(int a, int b) {
	int ans = 1;
	int base = a;
	while (b != 0) {
		if ((b & 1) != 0) { //如果当前的次幂数最后一位(二进制数)不为0的话，那么我们将当前权值加入到最后答案里面去
			ans = ans * base;
		}
		//权值增加
		base = base * base;
		b >>= 1;
	}
	return ans;
}
int main()
{
	printf("%d", fastPower(3, 11));
	return 0;
}

/*个人解析

为什么要快速幂？
更快的算出幂，由于一个指数肯定能够分解成二进制的形式，通过对二进制的最右边一位的判断，1则乘，否则则不乘
可以缩小计算次数，而且由于指数都被分解为2的i次方，所以权值可以通过累乘来记录，比如2^4 2^8 2^16都可以由前者乘以前者来得到。当遇到二进制上的1时候再乘就可以得到正确的答案。

快速幂是根据指数转为二进制，在二进制遇到1的地方对答案进行累乘，也即是在这个时候相当于乘1，所以基础
权值要不断的乘自己，来保证正确性。
例如3^11
由于任何数的零次方都是1，所以ans一开始为1
3^1*3^2*3^8  1 2 8想到二进制 3的1次方就是基础值乘3 1*3 (3^2=3^1*3^1) (3^4=3^2*3^2) (3^8=3^4*3^4)

11=1101
分为2^3+2^1+2^0 基础权值为3，一开始0位上有1，所以初始答案1要乘以当前的权值，所以ans*base=3 base为9
这个时候要计算第1位的权值了，，发现此时1位上也为1，所以ans*base=3*9=27 base为81（9*9）
计算第2位，，此时位置上为0，不乘,81*81=6561
最后一位，此时位置上有1,ans*base=27*6561=177147
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//求上下界
class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        int pre, last, l, r;
    // 下界
        for (l = 0, r = data.size() ;l < r; ) {
            int mid = (l + r) / 2;
            if (data[mid] >= k)
                r = mid;
            else
                l = mid + 1;
        }
        pre = r;

        // 上界
        for (l = -1, r = (int)data.size() - 1; l < r; ) {
            int mid = (l + r + 1) / 2;
            if (data[mid] <= k)
                l = mid;
            else
                r = mid - 1;
        }
        last = l;
        return last - pre + 1;
    }
};

伪丑数|Pseudo ugly number

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import java.io.BufferedInputStream;
import java.util.Arrays;
import java.util.Scanner;


public class Main {
    final static int N = 5842;//
    static long  [] humble = new long [N+5];
    
//    static int [] l = new int [N];
//    static int [] r= new int [N];
//    static float per[]=new float [N+1];
    public static void main(String args[])
    {
        Scanner in = new Scanner(new BufferedInputStream(System.in));
        humble[1]=1;
        int p2,p3,p5,p7;
        p2=p3=p5=p7=1;
        int i=1;
        while(i<=N)
        {
            i++;
            humble[i]=Math.min(Math.min(humble[p2]*2, humble[p3]*3),Math.min(humble[p5]*5, humble[p7]*7));
            if(humble[i]==humble[p2]*2)
                p2++;
            if(humble[i]==humble[p3]*3)
                p3++;
            if(humble[i]==humble[p5]*5)
                p5++;
            if(humble[i]==humble[p7]*7)
                p7++;
        }
        while(in.hasNext())
        {
            int n=in.nextInt();
            if(n==0) break;
            else {
                if(n%10==1&&n%100!=11)
                    System.out.println("The "+n+"st humble number is "+humble[n]+".");
                else if(n%10==2&&n%100!=12)
                    System.out.println("The "+n+"nd humble number is "+humble[n]+".");
                else if(n%10==3&&n%100!=13)
                    System.out.println("The "+n+"rd humble number is "+humble[n]+".");
                else
                    System.out.println("The "+n+"th humble number is "+humble[n]+".");
            }
        }
    }
}

相邻图形面积问题|Adjacent Graphics Area

image-20201027165335069

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/*解法的核心在于考虑了直方图两个相邻长方形AB之间的关系。如果前一个长方形A低后一个长方形B高，则A肯定不会是某个大长方形的终点，因为我们可以安全地在A后面添加更高的B，使大长方形的宽度加1。如果A高B低，则A是可能的终点，假设我们就用A当做终点，并且以该长方形的高度当做大长方形的高度，看看可以往前延伸多长。根据上面这两条性质，我们可以维护一个递增序列（实际为非递减，当前后两个长方形的高度一样时，前一个长方形同样也不可能是终点，在此为了解释方便假定前后高度都不一样），*/

import java.io.BufferedInputStream;
import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;


public class Main {
	final static int N = 100010;//
//	static float [] dp = new float [N];
	static int [] height = new int [N];
//	static float per[]=new float [N+1];
	public static void main(String args[])
	{
		Scanner in = new Scanner(new BufferedInputStream(System.in));
		Stack<Integer> stk = new Stack<Integer>();
		int i,j,res;
		while(in.hasNext())
		{
			int sum=in.nextInt();
			if(sum==0)
				break;
			else
			{
				stk.removeAllElements();
				for(i=1;i<=sum;i++)
				{
					height[i]=in.nextInt();
				}
				height[sum+1]=0;
				res=0;
				for(i=1;i<=sum;i++)
				{
					if(stk.isEmpty()||height[stk.peek()]<=height[i])
						stk.push(i);
					else {
						int temp=stk.pop();
						res=Math.max(res, height[temp]*(stk.isEmpty()?i-1:i-stk.peek()-1));
						--i;
					}
				}
			}
			System.out.println(res);
		}
	}
}

皇后问题|N-queen

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>  
#include <cstdio>  
#include <cstring>  

using namespace std;
int main()
{
	int a[5] = {0};
	int i = 1,g;
	a[i] = 1;
	int sum = 0;
	while (1)
	{
		g = 1;
		for (int k = i - 1; k >= 1; k--)
		{
			if (a[k] == a[i] || abs(a[i] - a[k]) == i - k)
				g = 0;
		}
		if (g&&i == 4)
		{
			sum++;
		}
		if (i < 4 && g) { i++; a[i] = 1; continue; }
		while (a[i] == 4 && i > 1) i--;
		if (a[i] == 4 && i == 1)break;
		else a[i]++;
	}
	printf("%d", sum);
	
}

矩阵快速幂|Matrix fast power

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
/*
问题描述
　　已知递推公式：

　　F(n, 1)=F(n-1, 2) + 2F(n-3, 1) + 5,

　　F(n, 2)=F(n-1, 1) + 3F(n-3, 1) + 2F(n-3, 2) + 3.

　　初始值为：F(1, 1)=2, F(1, 2)=3, F(2, 1)=1, F(2, 2)=4, F(3, 1)=6, F(3, 2)=5。
　　输入n，输出F(n, 1)和F(n, 2)，由于答案可能很大，你只需要输出答案除以99999999的余数。
输入格式
　　输入第一行包含一个整数n。
输出格式
　　输出两行，第一行为F(n, 1)除以99999999的余数，第二行为F(n, 2)除以99999999的余数。
样例输入
4
样例输出
14

21
数据规模和约定
　　1<=n<=10^18
*/
#include<bits/stdc++.h>  

using namespace std;  
typedef long long ll;  
const int mod=99999999;  
struct matrix  
{  
    ll a[8][8];  
};  
matrix multiply(matrix x,matrix y,int m,int n,int s)  
{  
    matrix tmp;  
    memset(tmp.a,0,sizeof(tmp.a));  
    for(int i=0;i<m;i++){  
        for(int j=0;j<n;j++){  
            for(int k=0;k<s;k++){  
                tmp.a[i][j]=(tmp.a[i][j] + (x.a[i][k] * y.a[k][j])%mod)%mod;  
            }  
        }  
    }  
    return tmp;  
}  
matrix tmp={  
                0,1,1,0,0,0,0,0,  
                1,0,0,1,0,0,0,0,  
                0,0,0,0,1,0,0,0,  
                0,0,0,0,0,1,0,0,  
                2,3,0,0,0,0,0,0,  
                0,2,0,0,0,0,0,0,  
                1,0,0,0,0,0,1,0,  
                0,1,0,0,0,0,0,1  
            };  
int main()  
{     
    matrix res;  
    ll f[8]={6,5,1,4,2,3,5,3};  //由f(n-1,1),f(n-1),2......f(n-3,1)..
								//假设n=4，则比例为f(3,1)....f(1,2)，比例则为651423，最后两个常数5,3
    ll sum1,sum2,n;  
    memset(res.a,0,sizeof(res.a));  
    for(int i=0;i<8;i++){  
        res.a[i][i]=1;  
    }  
    cin>>n;  
    if(n==1)  
        cout<<"2"<<endl<<"3"<<endl;  
    if(n==2)  
        cout<<"1"<<endl<<"4"<<endl;  
    if(n==3)  
        cout<<"6"<<endl<<"5"<<endl;  
    if(n>=4){  
        n-=3;  
        while(n) //矩阵快速幂   
        {  
            if(n&1) res=multiply(res,tmp,8,8,8);  
//&是位与操作符，n&1,不将n的二进制形式与00000000 00000001按位做与操作。这时，只							 //要//n的最右边一位是1，结果就不是0，为true，条件成立。所以这句话实际上就是if(n%2==1)
            n>>=1;  
            tmp=multiply(tmp,tmp,8,8,8);  
        }  
        sum1=0;  
        sum2=0;  
        for(int i=0;i<8;i++)  
        {  
            sum1=(sum1+(f[i]*res.a[i][0])%mod)%mod;  
            sum2=(sum2+(f[i]*res.a[i][1])%mod)%mod;  
        }  
        cout<<sum1<<endl;  
        cout<<sum2<<endl;  
    }  
    return 0;  
}

动态规划|Dynamic Planning

01背包|01 Pack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//背包问题：有m件物品和一个承重为t的背包。第i件物品的重量是w[i]，价值是v[i]。
//求解将哪些物品装入背包可使这些物品的重量总和不超过背包承重量t，且价值总和最大。
#include <stdio.h>
#include <conio.h>
#include <string.h>
 
int f[1010],w[1010],v[1010];//f记录不同承重量背包的总价值，w记录不同物品的重量，v记录不同物品的价值
 
int max(int x,int y){//返回x,y的最大值
    if(x>y) return x;
    return y;
}
 
int main(){
    int t,m,i,j;
    memset(f,0,sizeof(f));  //总价值初始化为0
    scanf("%d %d",&t,&m);  //输入背包承重量t、物品的数目m
    for(i=1;i<=m;i++)
        scanf("%d %d",&w[i],&v[i]);  //输入m组物品的重量w[i]和价值v[i]
    for(i=1;i<=m;i++){  //尝试放置每一个物品
        for(j=t;j>=w[i];j--){
            f[j]=max(f[j-w[i]]+v[i],f[j]);
            //在放入第i个物品前后，检验不同j承重量背包的总价值，如果放入第i个物品后比放入前的价值提高了，则修改j承重量背包的价值，否则不变
        }
    }
    printf("%d",f[t]);  //输出承重量为t的背包的总价值
    printf("\n");
    return 0;
}

多重背包|Multiple Pack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<stdio.h>
#include<string.h>
int dp[102];
int p[102],h[102],c[102];
int n,m;
void comback(int v,int w)//经费，重量。完全背包；
{
    for(int i=v; i<=n; i++)
        if(dp[i]<dp[i-v]+w)
            dp[i]=dp[i-v]+w;
}
void oneback(int v,int w)//经费，重量；01背包；
{
    for(int i=n; i>=v; i--)
        if(dp[i]<dp[i-v]+w)
            dp[i]=dp[i-v]+w;
}
int main()
{
    int ncase,i,j,k;
    scanf("%d",&ncase);
    while(ncase--)
    {
        memset(dp,0,sizeof(dp));
        scanf("%d%d",&n,&m);//经费，种类；
        for(i=1; i<=m; i++)
        {
            scanf("%d%d%d",&p[i],&h[i],&c[i]);//价值，重量，数量;
            if(p[i]*c[i]>=n) comback(p[i],h[i]);
            else
            {
                for(j=1; j<c[i]; j<<1)
                {
                    oneback(j*p[i],j*h[i]);
                    c[i]=c[i]-j;
                }
                oneback(p[i]*c[i],h[i]*c[i]);
            }
        }
        printf("%d\n",dp[n]);
    }
    return 0;
}

速记|note

完全背包:在当前体积下，是否要放入或者再放入一个当前物品i

01背包: 在当前体积下，是否要放入当前物品i

1
2
3
4
5
6
7
8
9
10
11
12
我们在做0-1背包，计算dp[i][j]的时候，需要用到前面的值，而这个值是前i-1个物品的值（相当于更新前i-1个物品的值）.
  
做完全背包，计算dp[j]时，我们需要更新的是当前状态，也就是前i个物品的值.(也就是说：用前i-1个的值和当前值比较，更新当前值).
  
可以这样理解:01背包是基于前一个物品的角度上考虑，考虑他是否需要放入当前的物品，
而由于当前的物品只有一个，又因为我们要参考前一个背包的状态，故而需要倒序。
0-1背包问题的状态转移方程是：f[i][j] = max(f[i-1][j], f[i-1][j - weight[i]] + value[i])
如果不是倒序，循环到后面的时候，参考前面的状态时就可能有当前物品的参与了，而当前物品只有一次，所以这样是不合理的。

而完全背包，有无限种可选，也即是，并非我这次选了，前面的就绝不可能一次没选过（可能选过，也可能没选），
因而基于前面的状态也就没有意义了，那么就基于当前的状态来考虑，比如拿一次当前的物品，
再拿一次当前的物品，等等等等。每次发生变化后都进行比较更新。

概率DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
import java.io.BufferedInputStream;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
	final static int N = 50005;//
	static double [] dp = new double [N];
	static int [] value = new int [N];
	static double [] per = new double [N];
//	static double per[]=new double [N+1];
	public static void main(String args[])
	{
		Scanner in = new Scanner(new BufferedInputStream(System.in));
		int times = in.nextInt();
		while(times!=0)
		{
			int i,j;
			int max=0;
			Arrays.fill(value, 0);
			Arrays.fill(per, 0.0);
			Arrays.fill(dp, 0.0);
			dp[0]=1.0;
			double p = in.nextDouble();
			p=1.0-p;
			int sum = in.nextInt();
			for(i=1;i<=sum;i++)
			{
				value[i]=in.nextInt();
				max+=value[i];
				per[i]=in.nextDouble();
				per[i]=1.0-per[i];
			}
			/*动态方程变化 多抢一个银行，其钱数必将转化为概率的乘积，所以动态方程也要做出改变。
			 最后遍历，剩余的钱数越多，说明所抢的钱数越少，
			 逃跑几率越大。所以从大到小遍历背包容量，
			 一旦大于p，即为最大概率跳出。*/
			for(i=1;i<=sum;i++)
			{
				for(j=max;j>=value[i];j--)
					dp[j]=Math.max(dp[j], dp[j-value[i]]*per[i]);
					/*使用钱数作为背包容量，通过1-p，即使用逃脱率，连续抢劫，逃脱率相乘则下降，这样才符合逻辑*/
					/*如，被抓率0.3,0.2抢劫两个为0.06，抢劫的越多被抓的几率越少这是不正常的，则逆向思维使用逃脱率*/
			}
			for(i=max;i>=0;i--)
			{
				if(dp[i]>=p)
				{
					System.out.println(i);
					break;
				}
			}
			times--;
		}
	}
}

矩阵相乘|Matrix Power

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <algorithm>
#include<cstring>
#define MAX 1050 
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
#define min(x,y) x<y?x:y
using namespace std;
long long M[MAX][MAX];
long long mart[MAX];
long long t;
void find(int n)
{
	int i, j, k;
	for (j = 2; j <= n; j++)
	{
		for (i = j - 1, M[i][i] = M[j][j] = 0; i>0; i--)
		{
			for (k = i; k<j; k++)
			{
				t = M[i][k] + M[k + 1][j] + mart[i - 1] * mart[k] * mart[j];
					M[i][j] = min(t, M[i][j]);
			}
		}
	}
}
int main(int argc, char *argv[]) {
	memset(M, 0x3f, sizeof(M));
	int i, n;
	cin >> n;
	for (i = 0; i <= n; i++)
	{
		cin >> mart[i];
	}
	find(n);
	cout << M[1][n];
	return 0;
}

常规DFS(island problem)

image-20201027165154352 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public int numIslands(char[][] grid) {
    //边界条件判断
    if (grid == null || grid.length == 0)
        return 0;
    //统计岛屿的个数
    int count = 0;
    //两个for循环遍历每一个格子
    for (int i = 0; i < grid.length; i++)
        for (int j = 0; j < grid[0].length; j++) {
            //只有当前格子是1才开始计算
            if (grid[i][j] == '1') {
                //如果当前格子是1，岛屿的数量加1
                count++;
                //然后通过dfs把当前格子的上下左右4
                //个位置为1的都要置为0，因为他们是连着
                //一起的算一个岛屿，
                dfs(grid, i, j);
            }
        }
    //最后返回岛屿的数量
    return count;
}

//这个方法会把当前格子以及他邻近的为1的格子都会置为1
public void dfs(char[][] grid, int i, int j) {
    //边界条件判断，不能越界
    if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0')
        return;
    //把当前格子置为0，然后再从他的上下左右4个方向继续遍历
    grid[i][j] = '0';
    dfs(grid, i - 1, j); //上
    dfs(grid, i + 1, j); //下
    dfs(grid, i, j + 1); //左
    dfs(grid, i, j - 1); //右
}

DFS+剪枝

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {
	public static int n;
	public static int sum;
	public static int flag=0;
	public static int max = -1;
	public static int min = 0x3f3f3f3f;
	public static int arr[];
	public static boolean vis[];

	public static void dfs(int pos, int nowlen, int target, int count) {
		if(flag==1)return;
		if(count==n) {flag=1;return;}
		for(int i=pos;i<=n;i++)
		{
			if(!vis[i]&&nowlen+arr[i]<=target)
			{
				vis[i]=true;
				if(nowlen+arr[i]==target)
					dfs(1, 0, target, count+1);
				else
				{
					dfs(i+1, nowlen+arr[i], target, count+1);
				}
				vis[i]=false;
				if(flag==1)return;//找到就返回
				if(nowlen==0)return;//因为起点是从nowlen=0，所以一开始的dfs才开始选用第一根木棍，如果前面的flag没满足，则
									//则证明选用了第一根但是发现第一根没有用得上，说明这个target是不可能成立的，因为有一根没用
									//所以直接返回，寻找下一个target
				while(i<n&&arr[i]==arr[i+1])i++;
				/*如果存在某些nowlen并不是为0，即为正在拼凑的过程中，前面的已拼凑的加上这一根没有满足，则说明跟这一个
				木棍相同的木棍肯定也在这个序列中无法被选中，也不用再去DFS了
				*/
			}
		}
	}

	public static void main(String[] args) {

		Scanner in = new Scanner(new BufferedInputStream(System.in));
		while (in.hasNext()) {
			int i, j;
			sum=0;
			n = in.nextInt();
			if (n == 0)
				break;
			arr = new int[n + 1];
			vis = new boolean[n + 1];
			for (i = 1; i <= n; i++) {
				arr[i] = in.nextInt();
				sum += arr[i];
			}
			for (i = 1; i <= n - 1; i++) {
				int k = i;
				for (j = i + 1; j <= n; j++)
					if (arr[j] > arr[i])
						k = j;
				if (k != i) {
					arr[k] ^= arr[i];
					arr[i] ^= arr[k];
					arr[k] ^= arr[i];
				}
			}
			max = arr[1];
			int temp = max;
			while (temp <= sum) {
				if (temp == sum)
					{System.out.println(sum);break;}
				else {
					while (sum % temp != 0) {//剪枝1，target必须可以被Sum整除
						temp++;
					}
					flag=0;
					dfs(1, 0, temp, 0);
					if(flag==1)
						{System.out.println(temp);break;}
				}
				temp++;
			}

		}

	}
}

Dijkstra+DFS

例题|Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
import java.io.BufferedInputStream;
import java.util.Arrays;
import java.util.Scanner;
 
/*小记:在第二个vis[j]的问题上，由于DJ算法是取未取过的，最小的距离值。所以求原点到某个点的距离的时候
如果一开始他们之间的直接距离就是最小的话，那么之后在经过各种别的点的出度到达当前点的距离肯定不会有直接
的这个距离大。所以也就没必要更新，（因为距离不可能为0），而如果距离大的话，那么这个点到最后才会更新。
也可以保证跟之前很多点比较之后最后的取值会是最小值*/
public class Main {
    public static int dp[];
    public static int dis[];
    public static int vis[];
    public static int map[][];
    public static int vsum,road;
    public static int INF=0x3f3f3f3f;//3f最好，0x7fffffff太大了，不适合DJ算法
    public static int N=1010;
    public static void dj(int start)//地杰斯特拉
    {
        int i,j,k=0;
        Arrays.fill(vis, 0);
        for(i=1;i<=vsum;i++)
            dis[i]=map[start][i];
        dis[start]=0;
        vis[start]=1;
        for(i=1;i<=vsum;i++)
        {
            int temp=INF;
            for(j=1;j<=vsum;j++)
            {
                if(vis[j]!=1&&dis[j]<temp)
                    temp=dis[k=j];//这里就是取最小的值，千万不能加Break；
            }
            if(temp==INF) break;
            vis[k]=1;
            for(j=1;j<=vsum;j++)
            {
                if(vis[j]!=1&&dis[j]>dis[k]+map[k][j])//这里的vis[j]!=1是为了剪枝，因为已经被vis过的顶点
						      //根据算法的巧妙性，之后要是还有其他出度关系到该点	
					//，那么他的距离一定比已经vis过的所记录的值要大，也就没必要更新

                    dis[j]=dis[k]+map[k][j];
            }
        }
    }
    public static int dfs(int v)
    {
        if(v==2) return 1;
        if(dp[v]!=-1) return dp[v];
        int sum=0;
        for(int i=1;i<=vsum;i++)
        {
            if(map[v][i]!=INF&&dis[v]>dis[i])
                sum+=dfs(i);
        }
        dp[v]=sum;
        return dp[v];
         
    }
    public static void main(String args[]) {
        Scanner in=new Scanner(new BufferedInputStream(System.in));
        while(in.hasNext())
        {
            vsum=in.nextInt();
            if(vsum==0)break;
            road=in.nextInt();
            dis=new int[vsum+1];
            dp=new int[vsum+1];
            vis=new int[vsum+1];
            map=new int[vsum+1][vsum+1];
            int i,j;
            for(i=1;i<=vsum;i++)
                for(j=1;j<=vsum;j++)
                    map[i][j]=(i==j?0:INF);
            Arrays.fill(dp,-1);
            int u,v,w;
            for(i=1;i<=road;i++)
            {
                u=in.nextInt();v=in.nextInt();w=in.nextInt();
                 
                map[u][v]=w;map[v][u]=w;
            }
            dj(2);
            System.out.println(dfs(1));
        }
    }
}

Bellman-Ford+DFS

例题|Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
import java.io.BufferedInputStream;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	public static int dp[];
	public static int dis[];
	public static boolean[] inq;
	public static int map[][];
	public static int vsum, road;
	public static int INF = 0x3f3f3f3f;
	public static int N = 1010;
	public static Queue<Integer> que = new LinkedList<Integer>();

	public static void spfa(int start) {
		int i;
		for (i = 1; i <= vsum; i++)
			dis[i] = INF;
		que.offer(start);
		dis[start] = 0;
		inq[start] = true;
		while (!que.isEmpty()) {
			int k=que.poll();
			inq[k]=false;
			for (i = 1; i <= vsum; i++) {
				if(dis[i]>dis[k]+map[k][i]){
					dis[i]=dis[k]+map[k][i];
					if(!inq[i])
					{
						que.offer(i);
						inq[i]=true;
					}
				}
			}
		}
	}

	public static int dfs(int v) {
		if (v == 2)
			return 1;
		if (dp[v] != -1)
			return dp[v];
		int sum = 0;
		for (int i = 1; i <= vsum; i++) {
			if (map[v][i] != INF && dis[v] > dis[i])
				sum += dfs(i);
		}
		dp[v] = sum;
		return dp[v];
	}

	public static void main(String args[]) {
		Scanner in = new Scanner(new BufferedInputStream(System.in));
		while (in.hasNext()) {
			vsum = in.nextInt();
			if (vsum == 0)
				break;
			road = in.nextInt();
			dis = new int[vsum + 1];
			dp = new int[vsum + 1];
			inq = new boolean[vsum + 1];
			map = new int[vsum + 1][vsum + 1];
			int i, j;
			for (i = 1; i <= vsum; i++)
				for (j = 1; j <= vsum; j++)
					map[i][j] = (i == j ? 0 : INF);
			Arrays.fill(dp, -1);
			int u, v, w;
			for (i = 1; i <= road; i++) {
				u = in.nextInt();
				v = in.nextInt();
				w = in.nextInt();

				map[u][v] = w;
				map[v][u] = w;
			}
			spfa(2);
			System.out.println(dfs(1));
		}
	}
}

DP+DFS

例题|Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
import java.io.BufferedInputStream;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Scanner;


public class Main {
	public static int location[] =new int [4];
	public static int dir[][] ={{0,-1},{1,0},{0,1},{-1,0}};
	public static int map[][];
	public static int sum[][];
	public static int dp[][];
	public static boolean flag;
	public static int n,k;
	public static int dfs(int x,int y)
	{
		if(dp[x][y]!=0) return dp[x][y];
		int i,j,xx,yy,l=0,temp;
		for(i=0;i<4;i++)
		{
			for(j=1;j<=k;j++)//最多走多少步 
			{
				xx=x+dir[i][0]*j;
				yy=y+dir[i][1]*j;
				if(xx>n||xx<1||yy>n||yy<1)continue;
				if(map[x][y]<map[xx][yy]){
				temp=dfs(xx, yy);
				l=Math.max(l,temp);
				}
			}
		}
		dp[x][y]=l+map[x][y];
		return dp[x][y];
		
	}
	public static void main(String args[])
	{
		
		Scanner in = new Scanner(new BufferedInputStream(System.in));
		while(in.hasNext())
		{
			 int i,j;
			 n=in.nextInt();
			 k=in.nextInt();
			 if(n==-1&&k==-1) break;
			 map=new int[n+1][n+1];
			 dp=new int[n+1][n+1];
			 for(i=1;i<=n;i++)
				for(j=1;j<=n;j++)
					map[i][j]=in.nextInt();
			 for(i=0;i<=n;i++){
			 Arrays.fill(dp[i], 0);
			 }
			 System.out.println(dfs(1, 1));
		}
		
	}
}

常规BFS(island problem)

image-20201027165154352 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
public int numIslands(char[][] grid) {
    //边界条件判断
    if (grid == null || grid.length == 0)
        return 0;
    //统计岛屿的个数
    int count = 0;
    //两个for循环遍历每一个格子
    for (int i = 0; i < grid.length; i++)
        for (int j = 0; j < grid[0].length; j++) {
            //只有当前格子是1才开始计算
            if (grid[i][j] == '1') {
                //如果当前格子是1，岛屿的数量加1
                count++;
                //然后通过bfs把当前格子的上下左右4
                //个位置为1的都要置为0，因为他们是连着
                //一起的算一个岛屿，
                bfs(grid, i, j);
            }
        }
    return count;
}

private void bfs(char[][] grid, int x, int y) {
    //把当前格子先置为0
    grid[x][y] = '0';
    int n = grid.length;
    int m = grid[0].length;
    //使用队列，存储的是格子坐标转化的值
    Queue < Integer > queue = new LinkedList < > ();
    //我们知道平面坐标是两位数字，但队列中存储的是一位数字，
    //所以这里是把两位数字转化为一位数字
    int code = x * m + y;
    //坐标转化的值存放到队列中
    queue.add(code);
    while (!queue.isEmpty()) {
        //出队
        code = queue.poll();
        //在反转成坐标值（i，j）
        int i = code / m;
        int j = code % m;
        if (i > 0 && grid[i - 1][j] == '1') { //上
            //如果上边格子为1，把它置为0，然后加入到队列中
            //下面同理
            grid[i - 1][j] = '0';
            queue.add((i - 1) * m + j);
        }
        if (i < n - 1 && grid[i + 1][j] == '1') { //下
            grid[i + 1][j] = '0';
            queue.add((i + 1) * m + j);
        }
        if (j > 0 && grid[i][j - 1] == '1') { //左
            grid[i][j - 1] = '0';
            queue.add(i * m + j - 1);
        }
        if (j < m - 1 && grid[i][j + 1] == '1') { //右
            grid[i][j + 1] = '0';
            queue.add(i * m + j + 1);
        }
    }
}

并查集|Disjoint Set Union

Find Gang

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <cstdio>  
int fa[1005], e[1005], n;

void UF_set()
{
	for (int i = 0; i <= n; i++)
	{
		fa[i] = i;
		e[i] = 0;
	}
}

int Find(int x)
{
	return x == fa[x] ? x : Find(fa[x]);
}

void Union(int a, int b)
{
	int r1 = Find(a);
	int r2 = Find(b);
	if (r1 != r2)
	{
		fa[r1] = r2;
		//合并时，若r2有敌人  
		if (e[r2] != 0)
		{
			//若r1也有敌人  
			if (e[r1] != 0)
				//则它们的敌人是朋友  
				Union(e[r1], e[r2]);
			else
				//否则，r2的敌人同时也是r1的敌人  
				e[r1] = e[r2];
		}
	}
}

int main()
{
	char s[2];
	int m, x, y, cnt = 0;
	scanf("%d %d", &n, &m);
	UF_set();
	for (int i = 0; i < m; i++)
	{
		scanf("%s %d %d", s, &x, &y);
		if (s[0] == 'F')
			Union(x, y);
		else
		{
			//找到x的祖先，和x同一帮派  
			x = Find(x);
			//若其祖先没有敌人，则将y当作其敌人，其实就是将y当作这个帮派的敌人  
			if (e[x] == 0)
				e[x] = y;
			//若其祖先有敌人，则敌人的敌人是朋友，将它的两个敌人合并  
			else
				Union(e[x], y);
			//对y的操作和对x的雷同  
			y = Find(y);
			if (e[y] == 0)
				e[y] = x;
			else
				Union(e[y], x);
		}
	}
	for (int i = 1; i <= n; i++)
		if (Find(i) == i)
			cnt++;
	printf("%d\n", cnt);
}

Infection

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<stdio.h>
#define MAX 30005

int a[MAX],pre[MAX];

int find(int x)
{
    if(x!=pre[x])

        //找到其祖先节点 
        pre[x] = find(pre[x]);  

    //由父节点继续向上递归查询 ,并将其父节点变成找到的 
    return pre[x]; 
}
void merge(int x,int y)
{
    //分别查询两点的祖先节点。 
    int prex = find(x);
    int prey = find(y);

    //如果二者的祖先节点不一致，那么任意让二者中某一个认另一个为祖先，保证同集合。

    if(prex == prey)
    {
        return ;
    } 
    //应该是祖先节点进行组合。而不是当前节点！ 
    pre[prey] = prex;  
    a[prex] += a[prey];     
}
int main()
{
    int n,m;
    int k,x,y;
    while(~scanf("%d%d",&n,&m))
    {
        if(n==0&&m==0)
        {
            return 0;
        } 
        for(int i=0;i<n;i++)
        {
            //先将自身作为祖先节点。 
            pre[i] = i;  
            a[i] = 1; 
        }
        for(int i=0;i<m;i++)
        {
            //给出集合每个集合人数，以及第一个人的编号 
            scanf("%d%d",&k,&x);
            k--;
            while(k--)
            {
                scanf("%d",&y);
                merge(x,y); 
            }    
        } 
        printf("%d\n",a[find(0)]);//find(0)是为了找到0的根a[0的根]代表a下有多少人，这些人跟0同根则会感染

    } 
    return 0;
}

Risk degree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <cstdio>
#include <cstring>
#include <cctype>
#include <string>
#include <set>
#include <iostream>
#include <stack>
#include <cmath>
#include <queue>
#include <vector>
#include <algorithm>
#define mem(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
#define N 100000+20
#define mod 10007
#define M 1000000+10
#define LL long long
using namespace std;
int u[N], v[N], pre[N];
int n, m, a, b;
void init() {
	for (int i = 0; i<n; i++) {
		pre[i] = i;
	}
}
int find(int x) {
	if (x == pre[x])
			return x; else {
		pre[x] = find(pre[x]);
		return pre[x];
	}
}
int mix(int x, int y) {
	int fx = find(x);
	int fy = find(y);
	if (fx != fy) {
		pre[fx] = fy;
		return 1;
	}
	return 0;
}
int judge()//判断a和b是否相连 {
	int fx = find(a), fy = find(b);
	if (fx == fy)
			return 1;
	return 0;
}
int main() {
	freopen("input.txt","r",stdin);
	//初始化
	scanf("%d%d", &n, &m);
	init();
	for (int i = 0; i<m; i++) {
		scanf("%d%d", &u[i], &v[i]);
		mix(u[i], v[i]);
		//加入并查集
	}
	scanf("%d%d", &a, &b);
	if (judge() == 0)//如果这两个不连通直接输出-1 {
		puts("-1");
		return 0;
	}
	int sum = 0;
	for (int i = 1; i <= n; i++)//枚举每一个点 {
		if (i == a || i == b)continue;
		//不能是所要求的的这个点，要查询的两个点不能删去，不然肯定					      //不通
		init();
		//重新初始化
		for (int j = 0; j<m; j++) {
			if (u[j] == i || v[j] == i)//去除这个点所在的边，去除后对整个图进行连接，如果
			//最后还能联通，即这两个点的根是同一个，就说明这个不						   //是关键点
			continue;
			mix(u[j], v[j]);
		}
		int fx = find(a), fy = find(b);
		if (fx != fy)
					sum++;
	}
	cout << sum << endl;
	return 0;
}

线段树|Interval Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
//http://acm.hdu.edu.cn/showproblem.php?pid=1166
#include <iostream>
#include <string>
using namespace std;
#define MAX_N 50000
string str;
int sum;
//记录总兵数
int num[MAX_N + 1] = {
	0
}
;
//记录各个兵营的兵数
typedef struct  node {
	int left;
	int right;
	int data;
	node* lchild;
	node* rchild;
	node() {
		left = right = data = 0;
	}
}
Tree;
Tree* CreateTree(int a, int b) {
	Tree* r;
	r = (Tree*)malloc(sizeof(Tree));
	r->left = a;
	r->right = b;
	if (a == b) {
		r->data = num[a];
		r->lchild = r->rchild = NULL;
	} else {
		int mid = (a + b) >> 1;
		r->lchild = CreateTree(a, mid);
		r->rchild = CreateTree(mid + 1, b);
		r->data = r->lchild->data + r->rchild->data;
	}
	return r;
}
void insert(Tree* r, int a, int b) {
	if (r->left == a && r->right == a) {
		r->data += b;
		return;
	}
	int mid = (r->left + r->right) >> 1;
	if (a <= mid) {
		insert(r->lchild, a, b);
	} else {
		insert(r->rchild, a, b);
	}
	r->data += b;
}
void find(Tree* r, int a, int b) {
	if (r->left == a && r->right == b) {
		sum += r->data;
		return;
	}
	int mid = (r->left + r->right) >> 1;
	if (b <= mid) {
		find(r->lchild, a, b);
	} else if (a>mid) {
		find(r->rchild, a, b);
	} else {
		find(r->lchild, a, mid);
		find(r->rchild, mid + 1, b);
	}
}
int main() {
	int t, n, x, y;
	int i;
	int ca = 0;
	freopen("input.txt","r",stdin);
	scanf("%d", &t);
	while (t--) {
		printf("Case %d:\n", ++ca);
		scanf("%d", &n);
		for (i = 1; i <= n; i++) {
			scanf("%d", &num[i]);
		}
		Tree* T;
		T = CreateTree(1, n);
		while (cin >> str) {
			if (str == "Query") {
				sum = 0;
				scanf("%d%d", &x, &y);
				find(T, x, y);
				printf("%d\n", sum);
			} else if (str == "Add") {
				scanf("%d%d", &x, &y);
				insert(T, x, y);
			} else if (str == "Sub") {
				scanf("%d%d", &x, &y);
				insert(T, x, -y);
			} else {
				break;
			}
		}
	}
	return 0;
}
Page View
⬆︎UP